package tree.test538;

import listbyorder.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/18 10:22
 */
public class Solution1 {

    List<Integer> record = new ArrayList<>();
    int index = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root == null) return root;
        inorder(root);
        // 改造数组
        int n = record.size();
        int[] dp = new int[n];
        dp[n - 1] = record.get(n - 1);
        for (int i = n - 2; i >= 0; i--) {
            dp[i] = record.get(i) + dp[i + 1];
        }
        // 跟新二叉树
        dfs(root, dp);
        return root;
    }

    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        record.add(root.val);
        inorder(root.right);
    }

    private void dfs(TreeNode root, int[] dp) {
        if (root == null) return;
        dfs(root.left, dp);
        root.val = dp[index++];
        dfs(root.right, dp);
    }
}
